This article provides a practical introduction to kernel discrepancies, focusing on the Maximum Mean Discrepancy (MMD), the Hilbert-Schmidt Independence Criterion (HSIC), and the Kernel Stein Discrepancy (KSD). Various estimators for these discrepancies are presented, including the commonly-used V-statistics and U-statistics, as well as several forms of the more computationallyefficient incomplete U-statistics. The importance of the choice of kernel bandwidth is stressed, showing how it affects the behaviour of the discrepancy estimation. Adaptive estimators are introduced, which combine multiple estimators with various kernels, addressing the problem of kernel selection. This paper corresponds to the introduction of my PhD thesis (Schrab, 2025a, Chapter 2) and is presented as a standalone article to introduce the reader to kernel discrepancies estimators. First, in Section 1, we define kernels, Reproducing Kernel Hilbert Spaces, mean embeddings and cross-covariance operators, and present kernel properties such as characteristicity, universality and translation invariance. Then, in Section 2, we introduce the Maximum Mean Discprecancy, the Hilbert-Schmidt Independence Criterion, and the Kernel Stein Discrepancy, as well as their estimators, and we discuss the importance of the choice of kernel for such measures. We then introduce a collection of statistics in Section 3, including the commonly-used complete statistics, as well as their incomplete counterparts which trade accuracy for computational efficiency. Finally, in Section 4, we construct adaptive estimators combining multiple statistics with various kernels, which is one method to address the problem of kernel selection.

Kernel techniques are among the most popular and powerful approaches of data science. Among the key features that make kernels ubiquitous are (i) the number of domains they have been designed for, (ii) the Hilbert structure of the function class associated to kernels facilitating their statistical analysis, and (iii) their ability to represent probability distributions without loss of information. These properties give rise to the immense success of Hilbert-Schmidt independence criterion (HSIC) which is able to capture joint independence of random variables under mild conditions, and permits closed-form estimators with quadratic computational complexity (w.r.t. the sample size). In order to alleviate the quadratic computational bottleneck in large-scale applications, multiple HSIC approximations have been proposed, however these estimators are restricted to $M=2$ random variables, do not extend naturally to the $M\ge 2$ case, and lack theoretical guarantees. In this work, we propose an alternative Nystr\"om-based HSIC estimator which handles the $M\ge 2$ case, prove its consistency, and demonstrate its applicability in multiple contexts, including synthetic examples, dependency testing of media annotations, and causal discovery.